public class LinkedList<E> {

    //定义链表中的节点类以及它的构造函数，重写toString方法，以便调试
    private class Node{
        public E e;
        public Node next;
        //Constructor
        public Node(E e, Node next) {
            this.e = e;
            this.next = next;
        }
        public Node(E e){
            this.e = e;
            this.next = null;
        }
        public Node(Node next){
            this.e = null;
            this.next = next;
        }
        public Node(){
            this.e = null;
            this.next = null;
        }
        @Override
        public String toString() {
            return e.toString();
        }
    }
    //对于一个链表，我们都有一个头结点和一个size来表示它的大小
//    private Node head;
    private Node dummyNode;
    int size;
    //初始化链表，头结点为空，链表长度为0
    public LinkedList(){
        dummyNode = new Node(null,null);
        size = 0;
    }
    //获取链表中的元素个数：
    public int getSize() {
        return size;
    }

    //返回链表是否为空：
    public boolean isEmpty(){
        return size==0;
    }

    //在链表头添加元素：
    public void addFirst(E e){
        /*
        Node node = new Node(e);
        node.next = head;
        head = node;
         */
        //这行代码与注释掉的三行代码意思相同
//        head = new Node(e,head);
        add(0,e);
        //加入节点之后，链表长度加一
        size++;
    }
    //在链表中间添加元素
    public void add(int index, E e){
        if(index<0 || index>size){
            throw new IllegalArgumentException("Add failed.Illegal index.");
        }

//        if(index == 0)
//            addFirst(e);
//        else{
//            Node prev = head;
//            for (int i = 0;i<index-1;i++){
//                prev = prev.next;
//            }
        Node prev = dummyNode;
        for (int i = 0;i< index;i++) {
            prev = prev.next;
        }
//            Node node = new Node(e);
//            node.next = prev.next;
//            prev.next = node;
            //这行代码与注释掉的三行代码意思相同
        prev.next = new Node(e,prev.next);
            //加入节点之后，链表长度加一
        size++;
        }
    //在链表末尾添加元素
    public void addLast(E e){
        add(size, e);
    }
    //链表遍历
    public E get(int index){
        if(index<0 || index>=size){
            throw new IllegalArgumentException("Add failed.Illegal index.");
        }
        Node cur = dummyNode.next;
        for (int i = 0;i < index; i++){
            cur = cur.next;
        }
        return cur.e;
    }

    //链表更新
    public void set(int index, E e){
        if(index<0 || index>=size)
            throw new IllegalArgumentException("Add failed.Illegal index.");
        Node cur = dummyNode.next;
        for (int i = 0;i < index; i++)
            cur = cur.next;
        cur.e = e;
    }

    //查找链表中是否有元素e
    public boolean contains(E e){
        Node cur = dummyNode.next;
        while (cur != null){
            if(cur.e.equals(e))
                return true;
            cur = cur.next;
        }
        return false;
    }

    //链表中删除index
    public E remove(int index){
        if(index<0 || index>=size){
            throw new IllegalArgumentException("Add failed.Illegal index.");
        }
        Node prev = dummyNode;
        for(int i = 0;i<index;i++){
            prev = prev.next;
        }
        Node retNode = prev.next;
        prev.next = retNode.next;
        retNode.next = null;
        size--;

        return retNode.e;
    }

    @Override
    public String toString(){
        StringBuilder res = new StringBuilder();

//        Node cur = dummyNode.next;
//        while (cur!=null){
//            res.append(cur+"->");
//            cur=cur.next;
//        }
        for (Node cur = dummyNode.next; cur != null ;cur = cur.next)
            res.append(cur+"->");

        res.append("NULL");
        return res.toString();
    }
}
